package com.algrithom.graph.bfs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

import javafx.util.Pair;

/**
 * 127. 单词接龙
 *
 * @author think
 * @version 1.0.0
 * @since 2020/5/10
 */
class Solution1 {
    
    private int length;
    
    private final Map<String,List<String>> allComboDict;
    
    Solution1(){
        this.length = 0;
        
        // Dictionary to hold combination of words that can be formed,
        // from any given word. By changing one letter at a time.
        this.allComboDict = new HashMap<>();
    }
    
    public static void main(String[] args){
        Solution1 solution1 = new Solution1();
        String beginWorld = "hit";
        String endWorld = "cog";
        List<String> worldList = Arrays.asList("hot","dot","dog","lot","log","cog");
        int count = solution1.ladderLength(beginWorld,endWorld,worldList);
        System.out.println("count is: " + count);
    }
    
    private int visitWordNode(Queue<Pair<String,Integer>> queue,Map<String,Integer> visited,Map<String,Integer> othersVisited){

        Pair<String,Integer> node = queue.remove();
        String word = node.getKey();
        int level = node.getValue();

        for (int i = 0; i < this.length; i++) {

            // Intermediate words for current word
            String newWord = word.substring(0,i) + '*' + word.substring(i + 1,length);

            // Next states are all the words which share the same intermediate state.
            for (String adjacentWord : this.allComboDict.getOrDefault(newWord,new ArrayList<>())) {
                // If at any point if we find what we are looking for
                // i.e. the end word - we can return with the answer.
                if (othersVisited.containsKey(adjacentWord)) {
                    return level + othersVisited.get(adjacentWord);
                }

                if (!visited.containsKey(adjacentWord)) {

                    // Save the level as the value of the dictionary, to save number of hops.
                    visited.put(adjacentWord,level + 1);
                    queue.add(new Pair<>(adjacentWord,level + 1));
                }
            }
        }
        return -1;
    }
    
    public int ladderLength(String beginWord,String endWord,List<String> wordList){

        if (!wordList.contains(endWord)) {
            return 0;
        }

        // Since all words are of same length.
        this.length = beginWord.length();

        wordList.forEach(word -> {
            for (int i = 0; i < length; i++) {
                String newWord = word.substring(0,i) + '*' + word.substring(i + 1,length);
                List<String> transformations = this.allComboDict.getOrDefault(newWord,new ArrayList<>());
                transformations.add(word);
                this.allComboDict.put(newWord,transformations);
            }
        });

        Queue<Pair<String,Integer>> beginQueue = new LinkedList<>();
        // BFS starting from endWord
        Queue<Pair<String,Integer>> endQueue = new LinkedList<>();
        beginQueue.add(new Pair<>(beginWord,1));
        endQueue.add(new Pair<>(endWord,1));

        // Visited to make sure we don't repeat processing same word.
        Map<String,Integer> visitedBegin = new HashMap<>();
        Map<String,Integer> visitedEnd = new HashMap<>();
        visitedBegin.put(beginWord,1);
        visitedEnd.put(endWord,1);

        while (!beginQueue.isEmpty() && !endQueue.isEmpty()) {

            // One hop from begin word
            int ans = visitWordNode(beginQueue,visitedBegin,visitedEnd);
            if (ans > -1) {
                return ans;
            }

            // One hop from end word
            ans = visitWordNode(endQueue,visitedEnd,visitedBegin);
            if (ans > -1) {
                return ans;
            }
        }

        return 0;
    }
}
